package Other;

import java.util.Arrays;

public class leet_31 {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 3, 2};

        Solution_31 p =new Solution_31();
        p.nextPermutationFunc1(nums);
        System.out.println(Arrays.toString(nums));
    }
}


class Solution_31 {
    /**
     * 第一种解题思路
     * 拆解题目方法
     * 1.找到一个比当前大的数  那么代表索引 i 必须与 i+n 进行交换 且 nums[i] < nums[i+n]
     * 2.找到一个比当前大的后一个的数，代表 i的位置必须足够靠右。而且 i+n 这个位置的数 min(nums[i+n]>nums[i])
     *   大于 nums[i] 且是在大于里面最小得一个
     * 3.发生转换行为后需要把后面的数字进行升序排列。保证换位之后的值是最小的。
     *
     * @param nums
     */
    public void nextPermutationFunc1(int[] nums) {
        if(nums.length<=1){
            return;
        }
        // 记录每一个位置的变换 没有变换就是本身
        int[] dp = new int[nums.length];
        boolean flag = false;

        for(int i=0; i<nums.length; i++){
            // 大于本值的最小值
            int minNowNum = nums[i];
            int minNowIndex = i;
            for(int j=i+1; j<nums.length; j++){
                int tmpNUm = nums[j];
                if(minNowNum==nums[i] && tmpNUm>minNowNum){
                    // 第一次只要比我大即可
                    minNowNum = tmpNUm;
                    minNowIndex=j;
                }else if(tmpNUm<minNowNum && tmpNUm>nums[i]){
                    // 一旦发生改变，目标就需要取大于我里面的最小值
                    minNowNum = tmpNUm;
                    minNowIndex=j;
                }
            }
            dp[i] = minNowIndex;
        }

        for(int i=dp.length-1; i>-1; i--){
            if(i != dp[i]){
                // 一旦这里发生转换代表找到
                int tmpNum = nums[i];
                nums[i] = nums[dp[i]];
                nums[dp[i]] = tmpNum;
                // 把后面的数 进行升序
                quickSort(nums, i+1, nums.length-1);
                flag = true;
                break;
            }
        }
        if(flag == false){
            // 进行快排
            quickSort(nums, 0, nums.length-1);
        }
    }


    /**
     * 进行快排
     */
    public void quickSort(int[] nums, int left, int right){
        if(left > right){
            return;
        }

        // 定义中间值
        int medium = nums[left];
        int i=left;
        int j=right;

        // 当i和j相遇时代表已经按照medium 排好顺序了
        while(i!=j){
            // 一定要优先移动右指针
            // 找到小于medium 值
            while(nums[j]>=medium && i<j){
                j--;
            }

            // 移动左指针
            // 找到大于medium的值
            while(nums[i]<=medium && i<j){
                i++;
            }

            // 相遇代表2边存在值需要交换
            if(i<j){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }

        // 当拍完顺序后代表medium 左边都是小于的 右边都是大于的
        // 将medium放到对应的位置i上
        nums[left] = nums[i];
        nums[i] = medium;

        // 由于i本身已经排好顺序了 需要排序 i的左边与右边
        quickSort(nums, left, i-1);
        quickSort(nums, i+1, right);
    }


}